package 算法.异或的妙用;

import java.util.Arrays;

/**
 * @author coderFu
 * @create 2022/3/8
 *
 * 使用异或找出 一个数组中出现次数为基数的两个数
 */
public class FindTwoBase {

    public static void main(String[] args){
        int[] arr = new int[]{1,1,1,1,2,2,2,3,3,3,3,4,5,5,5,5,6,6,6,6};

        selectTwoBase(arr);

        swap(arr,3,4);
        System.out.println(Arrays.toString(arr));


    }


    /**
     * 通过异或找到两个出现次数为奇数的数
     * @param arr
     */
    public static void selectTwoBase(int[] arr){

        int  eor = 0;
        for (int a : arr){
            // 每个数和eor进行异或 ，最终得到 两个基数的异或
            eor ^= a;
        }
        // System.out.println(eor);
        // 找到 eor 中 右边第一个 为 1 的数 本身与自己的取反加1

        int rightOne = eor & (~eor+1);
        System.out.println(rightOne);
        System.out.println("==================");
        int eor2 = 0;

        for (int a : arr){
            if ((a & rightOne) == rightOne){
               // System.out.println(a);
                eor2 ^= a;
            }
            // 找到 两个基数次数中的一个
        }
        System.out.println("两个基数出现的分别为："+eor2+",和"+(eor^eor2));
    }


    /**
     * 使用异或对两个数进行交换
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr, int i, int j){
        // 注意 两个数所在的位置不能一样
        if (i == j){
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}
